#include "BTreeNode.h"
#include <cstring> 

using namespace std;

/*
 * BTLeafNode constructor
 */
BTLeafNode::BTLeafNode()
{
    keyCount = 0;
    memset(buffer, 0, PageFile::PAGE_SIZE);
    setNextNodePtr(-1);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
	RC rc;
	
	if ((rc = pf.read(pid, buffer) < 0)) 
		return rc;
  
	// Key count for the node is saved at the start of the pagefile
	int* keyCountP = (int*) buffer;
	keyCount = keyCountP[0];
  
	dataBuffer = (KeyPairLeaf*)(buffer + sizeof(int) + sizeof(PageId));
  
	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
	// Write page to pagefile
	RC rc;
	if ((rc = pf.write(pid, buffer) < 0)) 
		return rc;
  
	return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	// Directly retrieve the key count, which is the first element of
	// the buffer array
	int value;
	memcpy(&value, buffer, sizeof(int));
	return value;
	
	// return keyCount;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	// Useful constants
	int tuple_size = sizeof(int) + sizeof(RecordId);
	int header_size = sizeof(int) + sizeof(PageId);
	
	// Figure out if the node is full, and return an error code if not
	// The node initially has getKeyCount() tuples and the header, and is
	// not full if we still have space for one more tuple
	int curr_size = tuple_size * getKeyCount();
	if(header_size + curr_size + tuple_size > PageFile::PAGE_SIZE)
	{
		// NOTE: Error codes are in the Bruinbase.h file
		return RC_NODE_FULL;
	}
	
	// Find the location of the first node with a key larger than ours
	// That node and all the ones after must be shifted to the right
	char* iter = &buffer[0];
	iter += header_size;
	int curr_key = 0;
	int copy_size = curr_size;
	
	while(iter)
	{
		// Copy the current tuple's key
		memcpy(&curr_key, iter, sizeof(int));
		
		// If the current key has a value of 0, the tuple is empty
		if(curr_key == 0)
			break;
		
		// If the current key has a value less than the insert key,
		// increment the iterator and the number of keys we've seen
		else if(curr_key < key)
		{
			iter += tuple_size;
			copy_size -= tuple_size;
		}
		
		// Otherwise, stop
		else
			break;
	}
	
	// Create a temporary buffer to store all the tuples that we will shift
	// right in the page, and clear those tuples
	char* temp = (char*) malloc(PageFile::PAGE_SIZE);
	if(curr_key > 0 && copy_size > 0)
	{
		memcpy(temp, iter, copy_size);
		memset(iter, 0, copy_size);
	}
	
	// Load the key-value pair
	memcpy(iter, &key, sizeof(int));
	iter += sizeof(int);
	memcpy(iter, &rid, sizeof(RecordId));
	iter += sizeof(RecordId);

	// Put back the shifted keys
	memcpy(iter, temp, copy_size);
	
	// Free memory
	free(temp);
	
	// Update key count
	int new_key_count = getKeyCount() + 1;
	memcpy(buffer, &new_key_count, sizeof(int));
	
	return 0; 
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. 
 *		This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
	// Useful constants
	int tuple_size = sizeof(int) + sizeof(RecordId);
	int header_size = sizeof(int) + sizeof(PageId);

	// Check the current size of this node, so we can split it in half
	int curr_size = tuple_size * getKeyCount();
	
	// Initialize iterator
	char* iter = &buffer[0];
	iter += header_size;	
	
	// Iterate to the halfway point of our buffer
	int copy_size = curr_size;
	int save_keys = 0;
	while(save_keys < getKeyCount() / 2)
	{
		iter += tuple_size;
		copy_size -= tuple_size;
		save_keys++;
	}
	
	// Allocate a buffer and move half of the tuples into it
	char* temp = (char*) malloc(PageFile::PAGE_SIZE);
	memcpy(temp, iter, copy_size);
	memset(iter, 0, copy_size);
	
	// Fill the sibling with the copied values
	memcpy(sibling.buffer + header_size, temp, copy_size);

	// Adjust the new sibling's number of keys
	int copy_keys = getKeyCount() - save_keys;
	memcpy(sibling.buffer, &copy_keys, sizeof(int));
	
	// Adjust this leaf node's number of keys
	memcpy(buffer, &save_keys, sizeof(int));
	
	// NOTE:	Leaf sibling pointers are assigned on the tree level
	//			rather than the root level
	
	// Free Memory
	free(temp);
	
	// Acquire the first sibling key to return in this function
	RecordId r_temp;
	if(sibling.readEntry(0, siblingKey, r_temp) != 0)
	{
		return RC_FILE_READ_FAILED;
	}
		
	// Insert the new tuple into the correct child
	if(key < siblingKey)
	{
		if(insert(key, rid) != 0)
		{
			return RC_FILE_WRITE_FAILED;
		}
	}
	else
	{
		if(sibling.insert(key, rid) != 0)
		{
			return RC_FILE_WRITE_FAILED;
		}		
	}
	
	return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or 
 *		equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
	// Useful constants
	int tuple_size = sizeof(int) + sizeof(RecordId);
	int header_size = sizeof(int) + sizeof(PageId);

	// Initialize iterator
	char* iter = &buffer[0];
	iter += header_size;
	
	// Initialize the eid counter
	int eid_count = 0;
	
	// Find the first value >= the search key
	int curr_key;
	while(iter)
	{
		// Copy the current tuple's key
		memcpy(&curr_key, iter, sizeof(int));
		
		// Find the first tuple with a key greater than or equal to the 
		// value of the search key
		if(curr_key >= searchKey)
		{
			eid = eid_count;
			return 0;
		}
		else
		{
			iter += tuple_size;
			eid_count++;
		}
	}
	
	// At this point, there is no such tuple in this child node
	// NOTE:	Should we attempt to seek the next child?
	//			How to do so is not clear, and not in the spec
	//			For now, we'll try to implement this on the next level
	/*
		RecordId next_child;
		memcpy(&next_child, buffer + sizeof(int), sizeof(RecordId));
		// TODO: Find out how to check the next child
		if(  )
		{
			// Run this function on the next child
	 		int eid_count_rest;
	 
			// If it succeeds, add on our eid_count to its eid count
			// and return 0
	
			// If it fails, return an error
		}
	 
		// If no more children, return an error
		else
			return RC_NO_SUCH_RECORD; 
	 */
	
	return RC_NO_SUCH_RECORD;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
  // Useful constants
	int tuple_size = sizeof(int) + sizeof(RecordId);
	int header_size = sizeof(int) + sizeof(PageId);
  
  // Make sure it doesn't go past the end of the node's pagefile
  if(eid >= MAX_KEYS)
    return -1;
  if(eid*(sizeof(int) + sizeof(RecordId)) + sizeof(key) + sizeof(RecordId) 
		> PageFile::PAGE_SIZE)
    return -1;
    
  char* keyPairPointer = (char*)(buffer + header_size + eid *(tuple_size));
  
  memcpy(&key, keyPairPointer, sizeof(int));
  keyPairPointer += sizeof(int);
  memcpy(&rid, keyPairPointer, sizeof(RecordId));
  return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
  // Stored at the front of the pagefile after count
  int rPid;
  memcpy(&rPid, buffer + sizeof(int), sizeof(PageId));
  return  rPid; 
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
  *(PageId*)(buffer + sizeof(int)) = pid;
  memcpy(buffer + sizeof(int), &pid, sizeof(PageId));
  return 0; 
}

/*
 * BTNonLeafNode constructor
 */
BTNonLeafNode::BTNonLeafNode()
{
    keyCount = 0;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
  RC rc;
  if ((rc = pf.read(pid, buffer) < 0)) return rc;
  // Key count for the node is saved at the start of the pagefile
  int* keyCountP = (int*) buffer;
  keyCount = keyCountP[0];
  
  dataBuffer = (KeyPairNonLeaf*)(buffer + sizeof(int) + sizeof(PageId));
  
  return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
  int* keyCountP = (int*) buffer;
  // Store the key count into the page 
  keyCountP[0] = keyCount;
  // Write page to pagefile
  RC rc;
  if ((rc = pf.write(pid, buffer) < 0)) return rc;
  
  return 0; 
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ return keyCount; }


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
  // Error, unintialized node
  if(keyCount == 0)
    return RC_END_OF_TREE;
  // Error, node is full
  if(keyCount == MAX_KEYS)
    return RC_NODE_FULL;
  
  char* iter = buffer + sizeof(int) + sizeof(PageId);
  int eid = 0;
  // Binary search for the correct entry
  for(; eid < keyCount; eid++) {
    // If the key is equal, we found the one we were looking for by luck
    if(*(int*)iter >= key) {
      break;
    }
    iter += sizeof(int) + sizeof(PageId);
  }
  
  if( eid < keyCount)
    memmove(iter + sizeof(int) + sizeof(PageId), iter, ((keyCount - eid) * (sizeof(int) + sizeof(PageId))));
  memcpy(iter, &key, sizeof(int));
  memcpy(iter + sizeof(int), &pid, sizeof(PageId));
  
  keyCount++;
  return 0; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. 
 *		This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. 
 *		This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, 
								 int& midKey)
{ 
  // Error, unintialized node
  if(keyCount == 0)
    return RC_END_OF_TREE;
    
  bool insertWasMiddle = false;
  int midIndex = (int)floor(keyCount/2.0);
  KeyPairNonLeaf* movePoint = dataBuffer + (midIndex);
  PageId midPageId;
  // If the new value will be inserted to the left of current middle
  if(key < movePoint->key) {
    // Adjust the middle one to left to balance
    movePoint--;
    midIndex--;
    // If the inserted key would have become the middle
    if(key > movePoint->key) {
      insertWasMiddle = true;
      midIndex++;
      movePoint++;
    }
  }
  // Save the middle key and adjust the movePointer to indicate what should
  //  be copied to the sibling
  if(insertWasMiddle) {
    midKey = key;
    midPageId = pid;
  }
  else {
    midKey = movePoint->key;
    midPageId = movePoint->pid;
    movePoint++;
  }
  
  // Intialize the sibling, the pointer from the middle is the leftmost
  //  pointer of the sibling now
  sibling.initializeRoot(midPageId, movePoint->key, movePoint->pid);
  movePoint++;
  // Insert all the values to the right of the movepoint
  while(movePoint != dataBuffer + (keyCount)) {
    sibling.insert(movePoint->key, movePoint->pid);
    movePoint++;
  }
  
  // Clean up the original node, clear out the copied pairs, adjust size
  memset(dataBuffer + midIndex,0, (keyCount - midIndex) * sizeof(KeyPairNonLeaf));
  // Midindex indicates the first pair to not be in anymore, all pairs
  //  inclusive of midIndex are gone
  keyCount = midIndex;
  
  // If the insert was the middle, then it was passed up instead of inserted
  // Otherwise, it needs to be inserted into the proper place
  if(!insertWasMiddle) {
    if(key > midKey)
      sibling.insert(key, pid);
    else
      insert(key, pid);
  }
  
  return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
  // Error, unintialized node
  if(keyCount == 0)
    return RC_END_OF_TREE;
  
  KeyPairNonLeaf* currPair;
  char* iter = buffer + sizeof(int) + sizeof(PageId);
  int eid = 0;
  // Binary search for the correct entry
  for(; eid < keyCount - 1; eid++) {
    // If the key is equal, we found the one we were looking for by luck
    if(searchKey <= *(int*)iter) {
      break;
    }
    iter += sizeof(int) + sizeof(PageId);
  }
  
  // Decide between the pointer after or the pointer before
  if(eid == 0 && searchKey < *(int*)iter) {
    // If it's the very first key, then the pointer is in
    //  a special location
    PageId* first = (PageId*)(buffer + sizeof(int));
    pid = *first;
  }
  else if(searchKey >= *(int*)iter) {
    memcpy(&pid, iter + sizeof(int), sizeof(PageId));
  }
  else if(searchKey < *(int*)iter) {
    // For the pointer before
    iter -= sizeof(int) + sizeof(PageId);
    memcpy(&pid, iter + sizeof(int), sizeof(PageId));
  }
  else {
    return RC_NO_SUCH_RECORD;
  }
  
  return 0; 
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
  int header_size = sizeof(int) + sizeof(PageId);
  char* pid1p = buffer + sizeof(int);
  *((PageId*)pid1p) = pid1;
  
  KeyPairNonLeaf* firstKeyPair = dataBuffer;
  memcpy((buffer + header_size), &key, sizeof(int));
  memcpy(buffer + header_size + sizeof(int), &pid2, sizeof(PageId));
  // Assume that the node is empty (non-initialized) beforehand
  keyCount = 1;
  return 0; 
}
